package day02;

/**
 * @author Jetwang
 * @version 1.0
 * @since 2023/3/2 20:14
 * 力扣 203
 */
public class LinkedListPractice03 {
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        // 加入哨兵
        ListNode s = new ListNode(-1, head);
        recursion(s, n);
        return s.next;
    }

    public static ListNode removeNthFromEnd02(ListNode head, int n) {
        // 加入哨兵
        ListNode s = new ListNode(-1, head);
        ListNode p1 = s;
        ListNode p2 = s;
        // 倒数第n+1节点
        for (int i = 0; i < n + 1; i++) {
            p2 = p2.next;
        }
        while (p2 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        p1.next = p1.next.next;
        return s.next;
    }

    private static int recursion(ListNode p, int n) {
        if (p == null) {
            return 0;
        }
        int nth = recursion(p.next, n); // 下一个节点位置
        if (nth == n) {
            p.next = p.next.next;
        }
        return nth + 1; // 当前节点倒数位置
    }

    public static void main(String[] args) {
        ListNode o5 = new ListNode(5, null);
        ListNode o4 = new ListNode(4, o5);
        ListNode o3 = new ListNode(3, o4);
        ListNode o2 = new ListNode(2, o3);
        ListNode o1 = new ListNode(1, o2);

        // removeNthFromEnd(o1, 5);
        removeNthFromEnd02(o1, 5);
        System.out.println(o1);
    }
}
